#include "bits/stdc++.h"
using namespace std;
using ll = long long;

unsigned seed;
unsigned rnd(){
	unsigned ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}

struct Barrett {
  using u32 = unsigned int;
  using u64 = unsigned long long;
  using u128 = unsigned __int128_t;
  static constexpr u128 s = u128(1) << 96;

  Barrett(const u32 P) : p_(P), m_((s - 1) / P + 1){}

  u32 div(u64 v) const {
    return (v * m_) >> 96;
  }

  u32 operator()(u64 v) {
    return v - u64(div(v)) * p_;
  }

  u128 m_;
  u32 p_;
};

void solve() {
  int n, k;
  cin >> n >> k >> seed;  

  Barrett bt(n);
  vector<int> a(n + 1), c1(n + 1), c2(n + 1), p(n + 1);
  for (int i = 1; i <= k; i++) {
    a[i] = bt(rnd()) + 1;
    if (!p[a[i]]) {
      p[a[i]] = i;
    } else {
      c1[a[i]]++;
      c2[a[i]]++;
    }
  }

  vector<int> stk;  
  for (int i = 1; i <= n; i++) {
    if (!p[i]) {
      continue;
    }
    while (!stk.empty() && stk.back() > p[i]) {
      stk.pop_back();
    }
    if (!stk.empty()) {
      c1[a[stk.back()]]++;
    }
    stk.push_back(p[i]);
  }

  stk.clear();
  for (int i = n; i >= 1; i--) {
    if (!p[i]) {
      continue;
    }
    while (!stk.empty() && stk.back() > p[i]) {
      stk.pop_back();
    }
    if (!stk.empty()) {
      c2[a[stk.back()]]++;
    }
    stk.push_back(p[i]);
  }

  for (int i = n; i >= 1; i--) {
    c1[i] += c1[i + 1];
  }

  for (int i = 1; i <= n; i++) {
    c2[i] += c2[i - 1];
  }

  int ans = 0, ret = -1;
  for (int i = 1; i <= n; i++) {
    if (p[i]) {
      continue;
    }
    int res = c1[i] + c2[max(0, i - 1)];
    if (res > ret) {
      ret = res;
      ans = i;
    }
  }

  cout << ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);

  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}